|
A redundant binary representation (RBR) is a numeral system that uses more bits than needed to represent a single binary digit so that most numbers have several representations. An RBR is unlike usual binary numeral systems, including two's complement, which use a single bit for each digit. Many of an RBR's properties differ from those of regular binary representation systems. Most importantly, an RBR allows addition without using a typical carry. When compared to non-redundant representation, an RBR makes bitwise logical operation slower, but arithmetic operations are faster when a greater bit width is used. Usually, each digit has its own sign that is not necessarily the same as the sign of the number represented. When digits have signs, that RBR is also a signed-digit representation. ==Conversion from RBR== An RBR is a place-value notation system. In an RBR, digits are ''pairs'' of bits, that is, for every place, an RBR uses a pair of bits. The value represented by a redundant digit can be found using a translation table. This table indicates the mathematical value of each possible pair of bits. As in conventional binary representation, the integer value of a given representation is a weighted sum of the values of the digits. The weight starts at 1 for the rightmost position and goes up by a factor of 2 for each next position. Usually, an RBR allows negative values. There is no single sign bit that tells if a redundantly represented number is positive or negative. Most integers have several possible representations in an RBR. Often one of the several possible representations of an integer is chosen as the "canonical" form, so each integer has only one possible "canonical" representation; non-adjacent form and two's complement are popular choices for that canonical form. An integer value can be converted back from an RBR using the following formula, where ''n'' is the number of digit and ''dk'' is the interpreted value of the ''k''-th digit, where ''k'' starts at 0 at the rightmost position: : The conversion from an RBR to ''n''-bit two's complement can be done in O(log(''n'')) time using a prefix adder. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「redundant binary representation」の詳細全文を読む スポンサード リンク
|